/* 221. 最大正方形 */
/**
 * @param {character[][]} matrix
 * @return {number}
 */

/* 
    dp[i][j] 以(i,j) 为右下顶点所能形成的最大正方形的边长
    maxSideLength 保存最大的正方形边长
    base 第一行和第一列的'1'坐标对应的dp[i][j]只能为1

    (i,j) 坐标为右下角所能形成的最大正方形的边长，取决与它的左边，上方
    斜上方 的项所能形成的最大正方形的边长 的最小值 + 1(自身长度)
*/
var maximalSquare = function (matrix) {
    let maxSideLength = 0 //相当于记录保持者
    const dp = new Array(matrix.length) //dp数组
    for (let i = 0; i < matrix.length; i++) {
        dp[i] = new Array(matrix[i].length).fill(0) //初始化为0
        for (let j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] == 1) {
                if (!i || !j) {
                    dp[i][j] = 1 //base 第一列和第一行的值为1
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                }
                maxSideLength = Math.max(maxSideLength, dp[i][j]) //更新记录
            }
        }
    }

    return maxSideLength * maxSideLength // 面积
};